package com.chj.gaoji.class05;

//https://blog.csdn.net/mkr67n/article/details/104139460
//https://blog.csdn.net/qq_43394643/article/details/98600832
//https://blog.csdn.net/qq_43394643/article/details/98654978
//https://blog.csdn.net/u011889952/article/details/44813593
public class Code01_SplitNumer {

	// n:被拆分的次数 m:每次拆分的最大数值
	public static int GetPartition(int n, int m) {
		// 当n=1或者m=1时，只有一种情况
		if (n == 1 || m == 1) {
			return 1;
		}
		// 当n < m 时，无意义，返回原式
		if (n < m) {
			return GetPartition(n, n);
		}
		// 当n == m 时， 拆分成fun(n, m-1)和1
		if (n == m) {
			return GetPartition(n, m - 1) + 1;
		} else {
			return GetPartition(n, m - 1) + GetPartition(n - m, m);
		}
		// 当 n > m 时，可以用m进行拆分，或者用比m小的数进行拆分
//		if (n > m) {
//			return GetPartition(n, m - 1) + GetPartition(n - m, m);
//		}
	}

	public static int GetPartitionDP_1(int n, int max) {
		int[][] ww = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++) {
				if (j == 1 || i == 1) {
					ww[i][j] = 1;

				} else {
					if (j == i)
						ww[i][j] = 1 + ww[i][j - 1];
					else if ((i - j) < j)
						ww[i][j] = ww[i - j][i - j] + ww[i][j - 1];
					else
						ww[i][j] = ww[i - j][j] + ww[i][j - 1];
				}
			}
		return ww[n][max];
	}

	public static int ways1(int n) {
		if (n < 1) {
			return 0;
		}
		return process(1, n);
	}

	// pre 裂开的前一个部分
	// rest 还剩多少值，需要去裂开，要求裂出来的第一部分，不要比pre小
	// 返回裂开的方法数
	public static int process(int pre, int rest) {
		if (rest == 0) {
			return 1; // 之前裂开的方案，构成了1种有效方法
		}
		if (pre > rest) {
			return 0;
		}
		int ways = 0;
		for (int i = pre; i <= rest; i++) { // i : rest第一个裂开的部分，值是多少
			ways += process(i, rest - i);
		}
		return ways;
	}

	public static int ways2(int n) {
		if (n < 1) {
			return 0;
		}
		int[][] dp = new int[n + 1][n + 1];
		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][0] = 1;
		}
		for (int pre = n; pre > 0; pre--) {
			for (int rest = pre; rest <= n; rest++) {
				for (int i = pre; i <= rest; i++) {
					dp[pre][rest] += dp[i][rest - i];
				}
			}
		}
		return dp[1][n];
	}

	public static int ways3(int n) {
		if (n < 1) {
			return 0;
		}
		int[][] dp = new int[n + 1][n + 1];
		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][0] = 1;
		}
		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][pre] = 1;
		}
		for (int pre = n - 1; pre > 0; pre--) {
			for (int rest = pre + 1; rest <= n; rest++) {
				dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
			}
		}
		return dp[1][n];
	}

	public static void main(String[] args) {
		int n = 4;
		System.out.println(GetPartition(n, n));
		System.out.println(GetPartitionDP_1(n, n));
		System.out.println(ways1(n));
		System.out.println(ways2(n));
		System.out.println(ways3(n));
		System.out.println();

		int n2 = 10;
		System.out.println(GetPartition(n2, n2));
		System.out.println(GetPartitionDP_1(n2, n2));
		System.out.println(ways1(n2));
		System.out.println(ways2(n2));
		System.out.println(ways3(n2));
		System.out.println();

		int n3 = 20;
		System.out.println(GetPartition(n3, n3));
		System.out.println(GetPartitionDP_1(n3, n3));
		System.out.println(ways1(n3));
		System.out.println(ways2(n3));
		System.out.println(ways3(n3));
		System.out.println();
	}
}
